<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**           
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.03.20
 */

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;cassert&gt;
#include &lt;algorithm&gt;
#include &lt;set&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)
#define fill(a, x) memset(a, x, sizeof(a))
#define sz(a) (int)(a).size()
#define mp make_pair

typedef pair&lt;int, int&gt; pii;

int n;

const int maxPrime = (int)2e4 + 10;
int pn, p[maxPrime], ps[maxPrime]; // all primes which are &lt;= maxPrime
int divisor[maxPrime]; // primes[divisor[X]] = smallest divisor of number X

#define P(x) (p[divisor[x]] == (x))

void precalcPrimes()
{
  fill(divisor, -1), pn = 0;
  for (int i = 2; i &lt; maxPrime; i++)
  {
    if (divisor[i] == -1)
      divisor[i] = pn, p[pn++] = i; 
    for (int tmp, j = 0; j &lt;= divisor[i] && (tmp = i * p[j]) &lt; maxPrime; j++)
      divisor[tmp] = j;
  }
}

int ans, sum, rn, r[maxPrime];
set &lt;pii&gt; s;

void go( int i, int n )
{
  assert(i + (ans - rn) &lt;= pn);
  if (rn &lt; ans && n &lt; ps[i + ans - rn] - ps[i])
    return;
  if (rn + 1 == ans)
  {
    assert(n &lt; maxPrime);
    if (!P(n))
      return;
    r[rn++] = n, n = 0;
  }
  if (n == 0)
  {
    printf("%d\n", rn);
    forn(i, rn)
      printf("%d%c", r[i], " \n"[i == rn - 1]);
    exit(0);
  }
  if (rn &gt;= ans)
    return;

  pii state = mp(((ans - rn) &lt;&lt; 15) + i, n);
  if (!s.insert(state).second)
    return;

  r[rn++] = p[i];
  go(i + 1, n - p[i]);
  rn--;
  go(i + 1, n);
}

int main()
{
  #define NAME "primpart"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  assert(scanf("%d", &n) == 1);
  precalcPrimes();
  forn(i, pn)
    ps[i + 1] = ps[i] + p[i];    

  while (sum + p[ans] &lt;= n)
    sum += p[ans++];
  for (; ans &gt; 0; ans--)
  {
    fprintf(stderr, "try ans = %d\n", ans);
    go(0, n);
  }
  puts("IMPOSSIBLE");
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
